module nade.octree;

import std.stdio;
import std.math;

import derelict.opengl.gl;

import nade.vector;
import nade.coordinate;
import nade.color;
import nade.primitive;
import nade.material;


class Octree {
	this(Material* material)
	{
		_root = new Branch(null, Node.ChildType.NNN, material);
		_box = Region3(0, 0, 0, 1, 1, 1);
	}

	void render(Vector3 eyePos)
	{
		const camPos = Coordinate3(cast(int)floor(eyePos.x), cast(int)floor(eyePos.y), cast(int)floor(eyePos.z));

		Color.YELLOW.render;
		renderBox(_box);

		glEnable(GL_TEXTURE_2D);
		Color.WHITE.render;
		_root.render(_box, camPos);
		glDisable(GL_TEXTURE_2D);
	}

	void cut(const Region3 box, Material* material)
	{
		auto locator = new Locator(box);
		locator.update(box);

		_root.cut(_box, box, material);
	}

	private {
		Branch	_root;
		Region3		_box;
	}


	class Block {
		this(Region3 box, Material* material)
		{
		}

		void render()
		{
			assert(_material !is null);
			glBindTexture(GL_TEXTURE_2D, _material.texture);
			renderSolidBox(box);
		}

		private {
			Region3				_box;
			Material*		_material;
		}
	}


	class Node {
		enum ChildType {
			NNN = 0,
			NNP = 1,
			NPN = 2,
			NPP = 3,
			PNN = 4,
			PNP = 5,
			PPN = 6,
			PPP = 7,
		}

		this(Branch parent, ChildType childType, Material* material)
		{
			_parent = parent;
			_childType = childType;
			_material = material;
		}

		void render(const Region3 box, const Coordinate3 camPos)
		{
		}

		Branch split()
		{
			assert(_parent !is null);

			auto r = new Branch(_parent, _childType, _material);
			_parent._children[_childType] = r;

			return r;
		}

		void cut(const Region3 box, const Region3 cbox, Material* material)
		{
			if(cbox.overlaps(box))
			{
				if(cbox.contains(box))
					_material = material;
				else
					split.cut(box, cbox, material);
			}
		}

		static Region3 childBox(const Region3 box, ChildType childType)
		{
			const m = (box.from + box.to)/2;
			switch(childType)
			{
				case ChildType.NNN: return Region3(box.from.x, box.from.y, box.from.z, m.x, m.y, m.z);
				case ChildType.NNP: return Region3(box.from.x, box.from.y, m.z, m.x, m.y, box.to.z);
				case ChildType.NPN: return Region3(box.from.x, m.y, box.from.z, m.x, box.to.y, m.z);
				case ChildType.NPP: return Region3(box.from.x, m.y, m.z, m.x, box.to.y, box.to.z);
				case ChildType.PNN: return Region3(m.x, box.from.y, box.from.z, box.to.x, m.y, m.z);
				case ChildType.PNP: return Region3(m.x, box.from.y, m.z, box.to.x, m.y, box.to.z);
				case ChildType.PPN: return Region3(m.x, m.y, box.from.z, box.to.x, box.to.y, m.z);
				case ChildType.PPP: return Region3(m.x, m.y, m.z, box.to.x, box.to.y, box.to.z);

				default:
			}

			assert(false);
		}

		private {
			Branch			_parent;
			ChildType		_childType;

			Block[]			_blocks;
		}
	}


	class Branch : Node {
		this(Branch parent, ChildType childType, Material* material)
		{
			super(parent, childType, material);

			foreach(k, ref child; _children)
				child = new Node(this, cast(ChildType)k, material);
		}

		override void render(const Region3 box, const Coordinate3 camPos)
		{
			if((box.center - camPos).diagonalModulus < box.width)
			{
				foreach(k, child; _children)
				{
					child.render(childBox(box, cast(ChildType)k), camPos);
				}
			}
			else
			{
				super.render(box, camPos);
			}
		}

		override Branch split()
		{
			assert(false);
		}

		Branch createParent(ChildType childType)
		{
			assert(_parent is null);

			_parent = _root = new Branch(null, ChildType.NNN, null);
			_childType = childType;
			_parent._children[childType] = this;

			switch(childType)
			{
				case Node.ChildType.NNN: _box.to.x += _box.to.x - _box.from.x; _box.to.y += _box.to.y - _box.from.y; _box.to.z += _box.to.z - _box.from.z; break;
				case Node.ChildType.NNP: _box.to.x += _box.to.x - _box.from.x; _box.to.y += _box.to.y - _box.from.y; _box.from.z += _box.from.z - _box.to.z; break;
				case Node.ChildType.NPN: _box.to.x += _box.to.x - _box.from.x; _box.from.y += _box.from.y - _box.to.y; _box.to.z += _box.to.z - _box.from.z; break;
				case Node.ChildType.NPP: _box.to.x += _box.to.x - _box.from.x; _box.from.y += _box.from.y - _box.to.y; _box.from.z += _box.from.z - _box.to.z; break;
				case Node.ChildType.PNN: _box.from.x += _box.from.x - _box.to.x; _box.to.y += _box.to.y - _box.from.y; _box.to.z += _box.to.z - _box.from.z; break;
				case Node.ChildType.PNP: _box.from.x += _box.from.x - _box.to.x; _box.to.y += _box.to.y - _box.from.y; _box.from.z += _box.from.z - _box.to.z; break;
				case Node.ChildType.PPN: _box.from.x += _box.from.x - _box.to.x; _box.from.y += _box.from.y - _box.to.y; _box.to.z += _box.to.z - _box.from.z; break;
				case Node.ChildType.PPP: _box.from.x += _box.from.x - _box.to.x; _box.from.y += _box.from.y - _box.to.y; _box.from.z += _box.from.z - _box.to.z; break;

				default: assert(false);
			}

			return _parent;
		}

		override void cut(const Region3 box, const Region3 cbox, Material* material)
		{
			if(cbox.overlaps(box))
			{
				foreach(k, child; _children)
				{
					const cb = childBox(box, cast(ChildType)k);
					child.cut(cb, cb.intersection(cbox), material);
				}
			}
		}

		private {
			Node		_children[8];
		}
	}


	class Locator {
		this(const Region3 box)
		{
			_node = _root;
			_box = this.outer._box;
		}

		void update(const Region3 box)
		{
			writefln("update: %d %d %d %d %d %d", box.from.x, box.from.y, box.from.z, box.to.x, box.to.y, box.to.z);
start:
			if(box.from.x < _box.from.x)
			{
				if(box.from.y < _box.from.y)
				{
					if(box.from.z < _box.from.z)
						expand(Node.ChildType.PPP);
					else
						expand(Node.ChildType.PPN);
				}
				else
				{
					if(box.from.z < _box.from.z)
						expand(Node.ChildType.PNP);
					else
						expand(Node.ChildType.PNN);
				}

				goto start;
			}

			if(box.from.y < _box.from.y)
			{
				if(box.from.z < _box.from.z)
					expand(Node.ChildType.NPP);
				else
					expand(Node.ChildType.NPN);

				goto start;
			}

			if(box.to.x > _box.to.x)
			{
				if(box.to.y > _box.to.y)
				{
					if(box.from.z < _box.from.z)
						expand(Node.ChildType.NNP);
					else
						expand(Node.ChildType.NNN);
				}
				else
				{
					if(box.from.z < _box.from.z)
						expand(Node.ChildType.NPP);
					else
						expand(Node.ChildType.NPN);
				}

				goto start;
			}

			if(box.to.y > _box.to.y)
			{
				if(box.from.z < _box.from.z)
					expand(Node.ChildType.PNP);
				else
					expand(Node.ChildType.PNN);

				goto start;
			}

			if(box.from.z < _box.from.z)
				expand(Node.ChildType.NNP);

middle:
			if((_box.to.x - _box.from.x) <= 1  ||  (_box.to.y - _box.from.y) <= 1  ||  (_box.to.z - _box.from.z) <= 1) return;

			const mx = (_box.from.x + _box.to.x)/2;
			const my = (_box.from.y + _box.to.y)/2;
			const mz = (_box.from.z + _box.to.z)/2;
			if(box.to.x <= mx)
			{
				if(box.to.y <= my)
				{
					if(box.to.z <= mz)
					{
						shrink(Node.ChildType.NNN);
						goto middle;
					}
					else if(box.to.z >= mz)
					{
						shrink(Node.ChildType.NNP);
						goto middle;
					}
				}
				else if(box.from.y >= my)
				{
					if(box.to.z <= mz)
					{
						shrink(Node.ChildType.NPN);
						goto middle;
					}
					else if(box.to.z >= mz)
					{
						shrink(Node.ChildType.NPP);
						goto middle;
					}
				}
			}
			else if(box.from.x >= mx)
			{
				if(box.to.y <= my)
				{
					if(box.to.z <= mz)
					{
						shrink(Node.ChildType.PNN);
						goto middle;
					}
					else if(box.to.z >= mz)
					{
						shrink(Node.ChildType.PNP);
						goto middle;
					}
				}
				else if(box.from.y >= my)
				{
					if(box.to.z <= mz)
					{
						shrink(Node.ChildType.PPN);
						goto middle;
					}
					else if(box.to.z >= mz)
					{
						shrink(Node.ChildType.PPP);
						goto middle;
					}
				}
			}
		}

		void cut(const Region3 box, Material* material)
		{
			_node.cut(_box, box, material);
		}

		private {
			void shrink(Node.ChildType childType)
			{
				auto branch = cast(Branch)_node;
				if(branch is null) _node = branch = _node.split();

				auto c = branch._children[childType];
				_box = Node.childBox(_box, childType);

				_node = c;

				assert((_box.to.x - _box.from.x) >= 1);
				assert((_box.to.y - _box.from.y) >= 1);
				assert((_box.to.z - _box.from.z) >= 1);

				writefln("shrink: %d %d %d %d %d %d", _box.from.x, _box.from.y, _box.from.z, _box.to.x, _box.to.y, _box.to.z);
			}

			void expand(Node.ChildType childType)
			{
				auto c = _node._parent;
				if(c is null)
				{
					auto branch = cast(Branch)_node;
					assert(branch !is null);

					c = branch.createParent(childType);
				}

				switch(childType)
				{
					case Node.ChildType.NNN: _box.to.x += _box.to.x - _box.from.x; _box.to.y += _box.to.y - _box.from.y; _box.to.z += _box.to.z - _box.from.z; break;
					case Node.ChildType.NNP: _box.to.x += _box.to.x - _box.from.x; _box.to.y += _box.to.y - _box.from.y; _box.from.z += _box.from.z - _box.to.z; break;
					case Node.ChildType.NPN: _box.to.x += _box.to.x - _box.from.x; _box.from.y += _box.from.y - _box.to.y; _box.to.z += _box.to.z - _box.from.z; break;
					case Node.ChildType.NPP: _box.to.x += _box.to.x - _box.from.x; _box.from.y += _box.from.y - _box.to.y; _box.from.z += _box.from.z - _box.to.z; break;
					case Node.ChildType.PNN: _box.from.x += _box.from.x - _box.to.x; _box.to.y += _box.to.y - _box.from.y; _box.to.z += _box.to.z - _box.from.z; break;
					case Node.ChildType.PNP: _box.from.x += _box.from.x - _box.to.x; _box.to.y += _box.to.y - _box.from.y; _box.from.z += _box.from.z - _box.to.z; break;
					case Node.ChildType.PPN: _box.from.x += _box.from.x - _box.to.x; _box.from.y += _box.from.y - _box.to.y; _box.to.z += _box.to.z - _box.from.z; break;
					case Node.ChildType.PPP: _box.from.x += _box.from.x - _box.to.x; _box.from.y += _box.from.y - _box.to.y; _box.from.z += _box.from.z - _box.to.z; break;

					default: assert(false);
				}

				_node = c;

				writefln("expand: %d %d %d %d %d %d", _box.from.x, _box.from.y, _box.from.z, _box.to.x, _box.to.y, _box.to.z);
			}
		}

		Node node() { return _node; }

		Region3 box() { return _box; }

		private {
			Region3				_box;
			Node			_node;
		}
	}
}
